1. Field of the Invention
The invention relates in general to automated design of integrated circuits, and more particularly, to the use of hierarchical circuit designs in the simulation of integrated circuits.
2. Description of the Related Art
As the product development cycles continue to shorten, there is a need for the makers of SPICE-like simulators to come up with new ways to quickly and accurately predict the system-wide behaviors of these exponentially denser and more complex analog integrated circuit designs. In order to simulate a system, it is important to have a complete description of the system and its components. Ordinarily, system descriptions are given structurally. That is, the description of a system sets forth instances of components and their interconnections. Descriptions of primitive components may be provided behaviorally. For instance, a mathematical description may be provided to describe the signals at the ports of the components.
FIG. 1 is an illustrative drawing of a lumped network in which components (circuit modules) connect to nodes through ports. The lumped network includes a collection of nodes and branches. A node is a point of interconnection for branches, and a branch is a path between two nodes. The term port as used in connection with the Verilog language commonly means a terminal or pin. A more formal definition of the term port is a pair of related terminals for which only two quantities are important, the port voltage and the port current. The port voltage is the potential difference between the two terminals, and the port current flows between the two terminals. The current into one terminal must exactly equal the current out of the other. As used herein, however, port means a terminal or pin. See K. Kundert and O. Zinke, The Designer's Guide to Verilog AMS, Kluwer Academic Publishers, 2004, pages 46-47.
In a hierarchical circuit representation, circuit modules are represented as calls to branch circuits or to leaf circuits. A computer readable hierarchical representation of a circuit design may include a hierarchy of software calls. Each call corresponds to a branch circuit or to a leaf circuit. A call is a computer program instruction that instructs a computer program that uses the hierarchical design during simulation, for example, to retrieve a called circuit. In this manner, a branch or leaf circuit model can be retrieved and utilized during simulation.
In a circuit design represented by a hierarchical data structure, opportunities may exist for more efficient simulation processing of redundant or duplicative circuit behaviors that are sometimes exhibited by structurally redundant subcomponents of the hierarchical circuit structure. Examples of integrated circuits which tend to exhibit extensive hierarchical data structure include high-density memory chips such as SRAMs, DRAMs, EEPROMs, etc. Parallel data processing systems and telecommunication systems also tend to have hierarchical structures with redundant subcomponents, for example.
FIG. 2 is an illustrative conceptual diagram of an example of a typical memory circuit design that has a repetitive structure. The memory circuit design includes 64,000 repetitive columns 202. Each of the columns includes 512 repetitive rows. Each row is represented by a row branch circuit 204 which in turn calls to a leaf circuit 206. The 512 repetitive rows in the column are connected together through respective nodes 208, and each node is driven by a respective sense amplifier 210.
More specifically, each row is a subcircuit that is a branch 204 in the design that includes an instance of the leaf circuit 206. The leaf circuit 206 is represented in the hierarchy structure as a call that instructs a simulator program processing the hierarchy to reference the leaf circuit instance. Thus, a single leaf circuit representation is stored, although it may be referenced by numerous calls throughout a circuit hierarchy representing a circuit design.
FIG. 3 is an illustrative drawing of a hierarchical data structure representation of the example memory circuit of FIG. 2. A top level circuit is designated as the Root which represents substantially all column sub-circuits as calls C1 to C64000, where call represents a column of the memory circuit. Each column includes a call to substantially the same row circuits from R1 to R512, each representing a row of the memory circuit. Each row includes a call to substantially the same leaf circuit. This example hierarchical representation shows that identical circuit components that are repeated throughout a design may be more efficiently represented in a hierarchical structure as calls to such repetitive components. In particular, in the Root level 308, there are 64000 substantially the same instances of the same column block, represented by calls C1 to C64000. At the row circuit block level 310, there are 512 substantially the same instances of the same leaf circuit, represented by calls R1 to R512 to the leaf circuit 312. At the leaf circuit level 312, there is only one instance of the leaf circuit 312.
Simulation of a circuit design often involves traversal of the circuit design from one node to another in order to evaluate some aspect of the design such as whether a node has a DC path to ground, whether a node is connected to a ground voltage source, whether a node has some initial condition or whether a node should be considered for dynamic partitioning, for example, within the design. For instance, a topological check of a circuit design may involve traversal of all DC paths of all circuit elements of a circuit design. In a circuit design represented as a hierarchical structure, a traverse of a circuit design during simulation may cross from one level of the circuit hierarchy to a different level of the circuit hierarchy.
Traversal of a hierarchical circuit design presents a special challenge since numerous distinct circuit elements may be represented in the design by references to a single element. For instance, each of the row elements R1 to R512 of the example design of FIG. 3 references the leaf circuit 312, and each reference represents a distinct occurrence of the leaf circuit in the circuit design. Moreover, references to different distinct circuit elements in a design may be embedded in different levels of a multi-level hierarchy. For example, each of the column elements C1 to C64000 of the root level block 308 of the design of FIG. 3 references the branch level row block 310 of the design, that includes row elements R1 to R512. Each reface to the row block 310 represents a distinct occurrence of the collection of row elements R1 to R512. However, typically, only one instance of the row block 310 is stored in the database that contains the circuit design hierarchy. Also, each of the branch level row elements R1 to R512 references the leaf circuit at the leaf circuit level of the design. Each reference to the leaf circuit 312 represents a distinct occurrence of the leaf circuit 312 in the design hierarchy. The challenge is to permit selective traversal of each and every circuit element of the design despite the fact that numerous distinct occurrences of any given circuit element may be represented by a single reference (e.g., branch circuit or leaf circuit) in the hierarchical structure that represents the circuit design.
One approach to circuit design traversal involves flattening a hierarchical circuit design structure. However, flattening an entire circuit design may be impractical in the case of large design databases, such as for a typical DRAM design, for example. More specifically, flattening an entire design may exhaust computational memory resources and may be too expensive in terms of computational time.
Another approach is to partially flatten a hierarchical design. For example, the UltraSim simulator produced by Cadence Design Systems, with a place of business at San Jose, Calif., used a partial flattening technique in which a ground node in a root circuit is identified, and then starting from that identified ground node, attempt is made to dig out all grounded “v” sources from the entire hierarchy. One shortcoming of this approach is that it can break or distort the original circuit design hierarchy.
Accurate simulation results for a hierarchical circuit design can be hampered by the fact that a property of an instance of a called circuit may depend upon a corresponding property of a higher level calling circuit, for example. Referring to FIG. 4, there is shown an illustrative drawing of a hypothetical hierarchical circuit design in which multiple root level subcircuits call the same leaf level circuit. More specifically, within a single root circuit there are four instances of the same subcircuit, labeled subcircuit 1, subcircuit 2, subcircuit 3 and subcircuit 4. All four instances call the same lower level leaf circuit. Assume that a simulation process seeks to identify DC paths to ground through traversal of the illustrated circuit design. The traversal process would determine that, although ports of subcircuits 1-2 have DC paths to ground through resistors R1 and R2, capacitors C1 and C2 block corresponding ports of subcircuits 3-4 from having DC paths to ground. If the DC path traversal of the root circuit was to result in marking the leaf circuit as having a DC path to ground (based upon the DC paths associated with subcircuits 1-2), then such marking would be correct for subcircuits 1-2 but not for subcircuits 3-4. On the other hand, if the DC path traversal of the root circuit was to result in marking the leaf circuit as not having a DC path to ground (based upon the DC paths associated with subcircuits 3-4), then such marking would be correct for subcircuits 3-4 but not for subcircuits 1-2. Thus, the state of the DC path to ground property for each of the higher level calling subcircuits 1-4 affects the state of the DC path to ground property of the leaf circuit that is called by these higher level calling subcircuits 1-4.
Efficiency in the simulation of a hierarchical design can be hampered by repeated traversals of the same called circuit, for example. Referring to FIG. 5, there is shown an illustrative drawing of another hypothetical hierarchical circuit design in which multiple root level subcircuits call the same leaf level circuit. More particularly, within a single root circuit there are four instances of the same subcircuit, labeled subcircuit 5, subcircuit 6, subcircuit 7 and subcircuit 8. All four instances call the same lower level leaf circuit. Assume that a simulation process requires traversal of the entire root circuit and all of its calls. Further assume that traversal begins at node C. One hypothetical example traversal involves stepping into the subcircuit 6 and then stepping down in the hierarchy to the leaf circuit, which is at a lower level of the hierarchy below the root level. The traversal process traverses the leaf circuit. Next, the traversal process steps back up in the hierarchy to node B, which is at the root level. The traversal steps into subcircuit 5, and then again steps down in the hierarchy to the leaf circuit, which is at a level of the hierarchy below the root level. Next, the traversal process steps back up in the hierarchy to node A, which is at the root level. In a similar manner, the hypothetical traversal further involves stepping into the subcircuit 7 and then stepping down in the hierarchy to the leaf circuit, a lower level of the hierarchy below the root level. The traversal process traverses the leaf circuit. Next, the traversal process steps back up in the hierarchy to node D, which is at the root level. The traversal steps into subcircuit 8, and then again steps down in the hierarchy to the leaf circuit. Next, the traversal process steps back up in the hierarchy to node E, which is at the root level. In this hypothetical example, the leaf circuit is traversed four times, which is inefficient.
Thus, there has been a need for an improved accurate and efficient approach to traversal of a circuit design represented in computer memory as a hierarchical structure. The present invention meets this need.